"""3. 找零钱问题（贪心解法）"""
def greedy_coin_change(amount, coins=[5, 2, 1]):
    """
    贪心算法解决找零钱问题
    目标：用最少的硬币找零n元钱

    对于硬币面额[5, 2, 1]，贪心算法可以得到最优解
    因为大面额总是小面额的倍数

    参数:
        amount: 需要找零的金额
        coins: 硬币面额列表（降序排列）

    返回:
        result: 每种硬币的数量字典
        total_coins: 总硬币数量
    """
    # 确保硬币面额按降序排列
    coins.sort(reverse=True)

    result = {}
    remaining = amount

    for coin in coins:
        if remaining >= coin:
            count = remaining // coin  # 最多能用的该面额硬币数量
            result[coin] = count
            remaining -= count * coin

    total_coins = sum(result.values())

    return result, total_coins


def brute_force_coin_change(amount, coins=[5, 2, 1]):
    """
    蛮力法解决找零钱问题（用于验证贪心解的正确性）
    尝试所有可能的组合，找出硬币数量最少的方案
    """
    from itertools import product

    coins.sort(reverse=True)
    min_coins = float('inf')
    best_combination = None

    # 计算每种硬币的最大可能数量
    max_counts = [amount // coin for coin in coins]

    # 生成所有可能的组合
    for counts in product(*[range(max_count + 1) for max_count in max_counts]):
        total = sum(count * coin for count, coin in zip(counts, coins))

        if total == amount:
            num_coins = sum(counts)
            if num_coins < min_coins:
                min_coins = num_coins
                best_combination = dict(zip(coins, counts))

    return best_combination, min_coins


def is_greedy_optimal(coins):
    """
    检查对于给定的硬币面额，贪心算法是否能保证最优解
    条件：每个面额都是比它小的面额的倍数
    """
    coins_sorted = sorted(coins, reverse=True)
    for i in range(len(coins_sorted) - 1):
        if coins_sorted[i] % coins_sorted[i + 1] != 0:
            return False
    return True


# 测试找零钱问题
print("=== 找零钱问题测试 ===")
test_amounts = [18, 27, 13, 8, 99]

for amount in test_amounts:
    print(f"\n找零 {amount} 元:")

    # 贪心算法解
    greedy_solution, greedy_count = greedy_coin_change(amount)
    print(f"贪心算法: {greedy_solution}, 硬币数量: {greedy_count}")

    # 蛮力法验证（对于小金额）
    if amount <= 50:  # 限制金额以避免计算时间过长
        brute_solution, brute_count = brute_force_coin_change(amount)
        print(f"蛮力算法: {brute_solution}, 硬币数量: {brute_count}")
        print(f"贪心算法是否最优: {greedy_count == brute_count}")
    else:
        print("金额过大，跳过蛮力法验证")

# 测试贪心算法的最优性条件
print(f"\n=== 贪心算法最优性分析 ===")
coin_systems = [
    [5, 2, 1],  # 标准系统（贪心最优）
    [10, 5, 2, 1],  # 标准系统（贪心最优）
    [4, 3, 1],  # 非标准系统（贪心可能不是最优）
    [6, 4, 1]  # 非标准系统（贪心可能不是最优）
]

for coins in coin_systems:
    optimal = is_greedy_optimal(coins)
    print(f"硬币系统 {coins}: 贪心算法{'能' if optimal else '不能'}保证最优解")

# 演示贪心算法失败的情况
print(f"\n=== 贪心算法失败案例 ===")


def demonstrate_greedy_failure():
    """
    演示贪心算法不是最优的情况
    硬币系统: [4, 3, 1]，找零6元
    """
    coins = [4, 3, 1]
    amount = 6

    # 贪心算法解
    greedy_sol, greedy_count = greedy_coin_change(amount, coins)

    # 最优解（通过蛮力法得到）
    optimal_sol, optimal_count = brute_force_coin_change(amount, coins)

    print(f"找零 {amount} 元，硬币系统: {coins}")
    print(f"贪心算法解: {greedy_sol}, 硬币数量: {greedy_count}")
    print(f"最优解: {optimal_sol}, 硬币数量: {optimal_count}")
    print(f"贪心算法比最优解多用了 {greedy_count - optimal_count} 个硬币")


demonstrate_greedy_failure()